/**
 * 
 */
package No101_200.No191_200.HouseRobber_198;
/** 
 * @author  作者 E-mail: ttljtw@qq.com
 * @date 创建时间：2017年3月2日 下午8:43:52 
 * @version 1.0 
 * @parameter  
 * @since  
 * @return  
 */
/**
 * @author 李敬
 *
 */
public class Solution {
	
	/*
	 * 动态规划
	 * 
	 * 这道题的本质相当于在一列数组中取出一个或多个不相邻数，使其和最大。
	 * 那么我们对于这类求极值的问题首先考虑动态规划Dynamic Programming来解，
	 * 我们维护一个一位数组dp，其中dp[i]表示到i位置时不相邻数能形成的最大和，
	 * 那么递推公式怎么写呢，我们先拿一个简单的例子来分析一下，比如说nums为{3, 2, 1, 5}，
	 * 那么我们来看我们的dp数组应该是什么样的，首先dp[0]=3没啥疑问，
	 * 再看dp[1]是多少呢，由于3比2大，所以我们抢第一个房子的3，当前房子的2不抢，
	 * 所以dp[1]=3，那么再来看dp[2]，由于不能抢相邻的，
	 * 所以我们可以用再前面的一个的dp值加上当前的房间值，
	 * 和当前房间的前面一个dp值比较，取较大值当做当前dp值，
	 * 所以我们可以得到递推公式dp[i] = max(num[i] + dp[i - 2], dp[i - 1]), 
	 * 由此看出我们需要初始化dp[0]和dp[1]，
	 * 其中dp[0]即为num[0]，dp[1]此时应该为max(num[0], num[1])，代码如下：
	 * */
	
    public int rob(int[] nums) {
        if(nums.length<=0){
            return 0;
        }
        int[] a = new int[nums.length];
        a[0] = nums[0];
        if(nums.length>=2){
            a[1] = Math.max(nums[1],nums[0]);
            for(int i = 2;i<nums.length;i++){
                a[i] = Math.max(a[i-1],a[i-2]+nums[i]);
            }
            return Math.max(a[nums.length-1],a[nums.length-2]);
        }
        return a[0];
    }

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
